'''
@Problem description:
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log(m+n)).
找两个排序好的数组的中位数使得复杂度O(log(m+n))

@For example:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0

nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
'''


class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        nums = []
        m = 0
        n = 0
        while (m < len(nums1) and n < len(nums2)):
            if (nums1[m] < nums2[n]):
                nums.append(nums1[m])
                m += 1
            else:
                nums.append(nums2[n])
                n += 1
        nums += nums1[m:]
        nums += nums2[n:]
        i = len(nums)
        if i % 2 == 1:
            return float(nums[int((i - 1) / 2)])
        else:
            return float((nums[int(i / 2)] + nums[int(i / 2) - 1]) / 2.0)

    def findMedianSortedArrays2(self, nums1, nums2):
        nums = nums1+nums2
        nums.sort()
        i = len(nums)
        if(i %2 == 1):
            return float(nums[int((i - 1) / 2)])
        else:
            return float((nums[int(i / 2)] + nums[int(i / 2) - 1]) / 2.0)